Data processing systems in the form of computer networks are increasingly common in the modern workplace. Such networks typically include multiple workstations and host or server devices that may be distributed over a vast geographical distance. Such networks contain nodes; each node includes a communications control unit, which is a unit that controls the transmission and reception of data in a network. The communications control unit may contain one or more ports. The node may also be a processing element, such as a workstation or a personal computer. A processing element may include one or more processors and memory. The communications control unit for the node may be included in the processing element.
Many different topologies exist for connecting multiple computers into a distributed data processing system. One common technique for interconnecting multiple computers within a data processing system is to arrange the nodes in a ring structure. One known ring system is the SCI (Scalable Coherent Interface) network, defined by the standard I.E.E.E. 1596-1992 (hereinafter SCI standard), well known to those of ordinary skill in the art, which specifies that nodes in a network communicate via unidirectional rings. Data is passed from one node to another node around the ring from its source address to its destination address in units called packets. The source address is the node that originates the packet and the destination address is the node that is to receive the packet.
As the size of a computer network increases, multiple inter-connected rings may be employed so that the bandwidth of a single ring does not create a bottleneck in communications within the network. The multiple rings in the network are interconnected via special nodes called agent nodes, also called bridges or switches. Data packets that need to travel from the source address across multiple rings to reach a destination address are transferred by an agent node from one ring in the network to another ring in the network. The communications control unit in an agent node has two or more ports in order to connect to two or more rings.
Under the SCI standard, any time a packet is successfully received by a destination node or an agent node, the receiving node places an echo packet onto the ring as an indication to the source node that the packet does not have to be re-transmitted onto that ring. As a result, ownership or responsibility for a packet is transferred from node to node. If the receiving node is an agent node, it assumes the responsibility for ensuring that the packet is sent to the next node. Only agent nodes and destination nodes send echo packets, not other intermediate nodes.
For the nodes in a network that conform to the SCI standard, the source node transmits a packet without knowing whether the destination node will have a buffer available to accept a packet. When a destination node or agent node cannot accept a packet, it sends a busy echo back to the sender, which may be a source or an agent node; the source or agent node must retry the transmission later. When the agent or destination node sends a non-busy echo back to the sender, this non-busy echo indicates that the destination node successfully accepted the packet.
Using this buffering design, it is possible for a forward progress problem to occur by a sending node always receiving a busy echo for its packets. This problem can occur if other sending nodes are sending packets to the same destination node or through the same agent node, and they happen to always be first with their packets The SCI standard solution to this problem is a buffer reservation system. When a destination or agent node returns a busy echo, it places a reservation tag of "A" or "B" in the echo packet. When the sending node, which may be a source or agent node, retries this packet, it includes this reservation tag in the packet, which instructs the destination or agent node to give this packet priority for the available buffers. The destination or agent node alternates between accepting the outstanding "A" packets and accepting the outstanding "B" packets. While accepting "A" packets, those new packets that cannot be accepted are given a busy echo with a "B" reservation tag. Once all the "A" packets are accepted, then "B" packets are accepted and the destination node responds to those new packets that cannot be accepted with a busy echo that has an "A" reservation tag. The destination or agent node does not keep track of how many "A" or "B" reservation tag packets are outstanding; instead, a stitch (time-out) mechanism is used to deduce that, for example, no more "A" packets are outstanding.
To guarantee fair access to destination node buffers, no single sending node should be allowed to flood a single destination node with new packets and demand that each packet be given a reservation tag. To address this fair access problem, some prior art buffering systems, which did not have agents connecting multiple rings, have used a Demand Reservation Rule that states "no given sending node, at a given time, may demand more than one reservation from any given receiving node."
This Demand Reservation Rule does not work for SCI standard because the SCI standard allows the use of agents. Because SCI topologies consist of multiple rings connected via agents, packets transmitted by a single source node destined for a number of destination nodes may be funneled through a single agent node on the source node's ring. An SCI source node is not aware that its packets are being funneled through an agent node, and an agent node can send an echo packet with a reservation back to the source node without the source node realizing that the reservation came from the agent node and not the destination node. Thus, a source node would demand more than one reservation from one agent node (which would violate the Demand Reservation Rule) without realizing it. Due to this limitation, the SCI standard uses a modified version of the Demand Reservation Rule that further restricts a sending node to demanding only one reservation at any given time, regardless of the distribution of packet destinations.
The SCI standard reservation system works well when the design of the communications control unit includes very few, such as one or two, receiving buffers. However, packet throughput and latency (the time to deliver a packet from the source node to the destination node) are impacted when the last few "A" (or "B") packets are outstanding and more buffers are available than there are "A" (or "B") packets. The destination node will continue to reject new packets and any "B" (or "A") packets with a busy echo until the very last "A" (or "B") packet is accepted even though the destination node has excess buffers available. Thus, when the receiving node has a large number of buffers, the SCI standard reservation system causes the buffers to be under utilized. The impact to throughput of rejecting packets, which must then be re-transmitted, can be significant when the communications control unit design includes four, eight or more buffers. As the desire for speed grows, designers of communications control units would like to increase the number of buffers, yet the prior art control units are not able to effectively take full advantage of a large number of buffers.
For the foregoing reasons, there is a need for a communications control unit which guarantees fair access to receiving node buffers yet still allows new and "A" packets to be received when in the "receiving B" state, and still allows new and "B" packets to be received when in the "receiving A" state.